package promote.brozen.algorithm.leetcode._056;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @author Brozen
 * @date 2020/9/5 4:12 PM
 * @email brozen@qq.com
 */
public class IntervalMerge {
    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0 || intervals.length == 1) {
            return intervals;
        }

        //  按start排序
        Arrays.sort(intervals, Comparator.comparingInt(is -> is[0]));

        int intervalCount = 1;
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] <= intervals[intervalCount - 1][1]) {
                intervals[intervalCount - 1][1] = Math.max(intervals[intervalCount - 1][1], intervals[i][1]);
            } else {
                intervals[intervalCount] = intervals[i];
                intervalCount++;
            }
        }

         return Arrays.copyOfRange(intervals, 0, intervalCount);
    }
}
